首先 746. Min Cost Climbing Stairs (easy)
https://leetcode.com/problems/min-cost-climbing-stairs/

70. Climbing Stairs 的進階版本
    就是把每一階的階梯加上能量，要花費最少能量爬到最高階，每次只能走1~2步。

想法：

1. 一定是dp(都階梯了還不dp?)
2. 一樣爬到第一階跟第二階直接輸入在dp裡面([0,0])
3. 從第三階開始比較，從第一階爬到第三階跟從第二階爬到第三階，哪個能量花費低，取少的那個
4. 循環，結束

class Solution:
    #找出到該點的最小cost是多少
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        end = len(cost)+1
        dp = [0]*(end)
        for i in range(2,end):
            dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
            print(dp)
        return dp[-1]

再來是 62. Unique Paths (medium)
https://leetcode.com/problems/unique-paths/

這題喔，誒都，台灣的高中生誰不會的，學測數學成績應該很低吧XD

簡單來說有個棋盤(mxn)，有個人在左上角，有幾種方法可以走到右下角
所以答案一定是 (m+n)!/(m!n!) 結束。
老實說不會用dp解，但為了練習還是寫了一下。

from math import factorial as f
class Solution:
    #自己動手尻階層
    def uniquePaths(self, m: int, n: int) -> int:
        def cal(x):
            t = 1
            while x:
                t*=x
                x-=1
            return t
        return cal(m+n-2)//cal(m-1)//cal(n-1)
    
    #用python裡面的函式庫算階層
    def uniquePaths(self, m: int, n: int) -> int:
        return f(m+n-2)//f(m-1)//f(n-1)
    
    #dp寫法
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0 for i in range(n)] for i in range(m)]
        for i in range(m):
            for j in range(n):
                if i==0 or j==0:
                    dp[i][j] = 1
                else:    
                    dp[i][j] = dp[i-1][j]+dp[i][j-1]
        return dp[-1][-1]

再來是 438. Find All Anagrams in a String (medium)
https://leetcode.com/problems/find-all-anagrams-in-a-string/

題目會給一個s以及p，假設p的長度為len
要從s[i]~s[i+len-1]之間尋找有沒有p(順序不論)，然後輸出每個i數值。

想法：

1. sliding window，慢慢的把區段從0滑到最後
2. 每次滑到下一個的時候比較，是否有p存在
   老實說想法很簡單，但寫法會造就是否TLE，像第一個寫法，每往下移一次，就重新做一個counter，完全不管時間複雜度會直接爆掉。
   接下來就是改成，每新增一個元素，就移除一個舊元素再比較，就可以通過了。
   然後我有看到有人用hash的寫法但，老實說我不會這樣寫，不過滿有趣的就偷偷收錄ㄌ。

class Solution:
    #簡單來說，就是在s裡面從 i ~ + len(p)的地方找說有沒有p(順序不管)
    #TLE
    def findAnagrams(self, s: str, p: str) -> List[int]:
        pC = Counter(p)
        pL = len(p)
        ans = []
        for i in range(pL,len(s)+1):
            # print(s[i-pL:i])
            if Counter(s[i-pL:i]) == pC :
                ans.append(i-pL)
        return ans
    
    #略為改版
    def findAnagrams(self, s: str, p: str) -> List[int]:
        pL = len(p)
        sL = len(s)
        if sL < pL:
            return []
        pC = Counter(p)
        ans = []
        temp = Counter(s[0:pL])
        if temp == pC:
            ans.append(0)
        for i in range(pL+1,len(s)+1):
            # print(temp,pC)
            temp[s[i-pL-1]]-=1
            if temp[s[i-pL-1]] == 0:
                del temp[s[i-pL-1]]
            if s[i-1] not in temp:
                temp[s[i-1]] = 1
            else:
                temp[s[i-1]]+=1
            if temp == pC:
                ans.append(i-pL)
        return ans
    #再改版
    def findAnagrams(self, s: str, p: str) -> List[int]:
        pL = len(p)
        sL = len(s)
        if sL < pL:
            return []
        pDD = defaultdict(int)
        ans = []
        for i in p:
            pDD[i] += 1 #計算到底有多少個東西
        for i in s[:pL]:
            pDD[i] -= 1 #扣完就是數量有對上
        # if set([i for i in pDD.values()]) == {0}:
        if all(i==0 for i in pDD.values()):    
            ans.append(0)
        for i in range(pL+1,sL+1):
            if s[i-pL-1] in pDD:
                pDD[s[i-pL-1]]+=1
            if s[i-1] in pDD:
                pDD[s[i-1]]-=1
            # if set([i for i in pDD.values()]) == {0}: #檢查每一個是否都是0 #set
            if all(i==0 for i in pDD.values()):#檢查每一個是否都是0 #all
                ans.append(i-pL)
        return ans
        
    #神奇寫法，獲取hash值利用+-完成
    def findAnagrams(self, s: str, p: str) -> List[int]:
        pL = len(p)
        sL = len(s)
        if sL < pL:
            return []
        ans = []
        correctVal = sum(map(hash,p))
        currentVal = sum(map(hash,s[0:pL]))
        if correctVal == currentVal:
            ans.append(0)
        for i in range(pL+1,len(s)+1):
            currentVal -= hash(s[i-1-pL])
            currentVal += hash(s[i-1])
            if correctVal == currentVal:
                ans.append(i-pL)
        return ans